package site.wanjiahao;

public class KMP {

    // 蛮力算法
    static int indexOf(String text, String pattern) {
        if (text == null || pattern == null ||
                text.isEmpty() || pattern.isEmpty() ||
                pattern.length() > text.length()) return -1;

        char[] texts = text.toCharArray();
        char[] patterns = pattern.toCharArray();
        // 模式串初始索引
        int pi = 0, ti = 0;
        int pln = pattern.length();
        int tln = text.length();
        // 构造next表
        int[] next = next(patterns);
        while (pi < pln && ti - pi <= tln - pln) {
            if (pi < 0 || texts[ti] == patterns[pi]) {
                ti++;
                pi++;
            } else {
                // 不相等
                pi = next[pi];
            }
        }
        return pi == pln ? ti - pi: -1;
    }

    private static int[] next(char[] patterns) {
        int len = patterns.length;
        int[] next = new int[len];
        int i = 0;
        int n = next[i] = -1;
        int imax = len - 1;
        while (i < imax) {
            if (n < 0 || patterns[i] == patterns[n]) {
                i++;
                n++;
                if (patterns[i] == patterns[n]) {
                    next[i] = next[n];
                } else {
                    next[i] = n;
                }
            } else {
                n = next[n];
            }
        }
        return next;
    }

    private static int[] next1(char[] patterns) {
        int len = patterns.length;
        int[] next = new int[len];
        int i = 0;
        int n = next[i] = -1;
        int imax = len - 1;
        while (i < imax) {
            if (n < 0 || patterns[i] == patterns[n]) {
                // 如果nex他[i] = next[n]就没必要比较
                next[++i] = ++n;
            } else {
                n = next[n];
            }
        }
        return next;
    }

}
